package leetcode.biweekly.week102;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

import leetcode.helper.H;

public class Graph {
	List<List<Integer>> nexts;
	long[][] cost;
	int n;

	public Graph(int n, int[][] edges) {
		this.n = n;
		nexts = new ArrayList<>();
		cost = new long[n][n];
		for (int i = 0; i < n; i++) {
			nexts.add(new ArrayList<>());
		}
		for (int[] e : edges) {
			int f = e[0], t = e[1], c = e[2];
			cost[f][t] = c;
			nexts.get(f).add(t);
		}
	}

	public void addEdge(int[] edge) {
		int f = edge[0], t = edge[1], c = edge[2];
		cost[f][t] = c;
		nexts.get(f).add(t);
	}

	public int shortestPath(int node1, int node2) {
		if (node1 == node2) {
			return 0;
		}
		long[] dp = new long[n];
		Arrays.fill(dp, Long.MAX_VALUE);
		PriorityQueue<long[]> queue = new PriorityQueue<long[]>((a, b) -> Long.compare(a[1], b[1]));
		queue.add(new long[] { node1, 0 });
		while (!queue.isEmpty()) {
			long[] cur = queue.poll();
			long node = cur[0], c = cur[1];
			if (c > dp[(int) node]) {
				continue;
			}
			List<Integer> next = nexts.get((int) node);
			for (int nxt : next) {
				long cos = cost[(int) node][nxt];
				long nxtcos = cos + c;
				if (nxtcos < dp[nxt]) {
					dp[nxt] = nxtcos;
					queue.add(new long[] { nxt, nxtcos });
				}
			}
		}
		return dp[node2] == Long.MAX_VALUE ? -1 : (int) dp[node2];
	}

	public static void main(String[] args) {
		Graph g = new Graph(13, H.str2array1(
				"[[11,6,84715],[7,9,764823],[6,0,315591],[1,4,909432],[6,5,514907],[9,6,105610],[3,10,471042],[7,10,348752],[5,11,715628],[6,1,973999],[8,7,593929],[7,6,64688],[6,4,741734],[10,1,894247],[9,7,81181],[2,11,75418],[12,2,85431],[7,2,260306],[11,9,640614],[2,3,648804],[4,12,568023],[0,8,730096],[9,11,633474],[3,6,390214],[1,10,117955],[9,8,222602],[10,7,689294]]"));
		g.addEdge(H.str2array3("[1,2,36450]"));
		g.addEdge(H.str2array3("[8,0,709628]"));
		g.addEdge(H.str2array3("[2,4,30185]"));
		g.addEdge(H.str2array3("[12,1,21696]"));
		g.addEdge(H.str2array3("[1,8,2553]"));
		g.addEdge(H.str2array3("[4,6,2182]"));
		g.addEdge(H.str2array3("[7,5,206]"));
		g.addEdge(H.str2array3("[5,7,140]"));
		g.addEdge(H.str2array3("[12,6,365184]"));
		g.addEdge(H.str2array3("[3,2,5]"));
		g.addEdge(H.str2array3("[0,11,5]"));
		g.addEdge(H.str2array3("[1,7,5]"));
		H.print(g.shortestPath(11, 11));
	}
}
